package com.jjlin.chapter_8;

import java.util.*;
public class CD14{

    // 书本上的解法，时间复杂度为O(NlogN)，空间复杂度为O(N)
    public static int getMaxLength(int[] arr, int k){
        if(arr == null || arr.length == 0)
            return 0;
        int n = arr.length;
        int sum = 0;
        int[] helpArr = new int[n + 1];
        for(int i = 0; i < n; i++){
            sum += arr[i];
            helpArr[i + 1] = Math.max(sum, helpArr[i]);
        }
        sum = 0;
        int len = 0;
        int res = 0;
        int index;
        for(int i = 0; i < n; i++){
            sum += arr[i];
            index = getLessIndex(helpArr, sum - k);
            len = index == -1 ? 0 : i - index + 1;
            res = Math.max(len, res);
        }
        return res;
    }

    // 二分查找出大于等于num的最早位置，如果都小于num则返回-1
    public static int getLessIndex(int[] arr, int num){
        int low = 0;
        int mid;
        int high = arr.length - 1;
        int res = -1;
        while(low <= high){
            mid = low + ((high - low) >> 1);//一定要注意移位运算的优先级低于加法运算，因此要加括号
            if(arr[mid] >= num){
                res = mid;
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return res;
    }

    //讨论区大佬们的做法，时间复杂度达到O(N)，空间复杂度为O(N)
    public static int getMaxLength1(int[] arr, int k){
        int n = arr.length;
        int[] minSum = new int[n]; //从后往前扫描计算对应位置i的最小累加和
        int[] ends = new int[n]; //用来记录当前位置所对应的累加和的结束位置
        minSum[n - 1] = arr[n - 1];
        ends[n - 1] = n - 1;
        for(int i = n - 2; i >= 0; i--){
            if(minSum[i + 1] <= 0){
                minSum[i] = arr[i] + minSum[i + 1];
                ends[i] = ends[i + 1];
            }else{
                minSum[i] = arr[i];
                ends[i] = i;
            }
        }
        int len = 0, end = 0, sum = 0;
//        for(int i = 0; i < n; i++){
//            while(end < n && (sum + minSum[end] <= k)){
//                sum += minSum[end];
//                end = ends[end] + 1;
//            }
//            len = Math.max(len, end - i);
//            sum -= end > i ? arr[i] : 0;
//            end = Math.max(i + 1, end);
//        }
        //以上的for循环还可以改写如下
        int cur = 0, start = 0;
        while(cur < n){
            sum += minSum[cur];
            if(sum <= k){
                len = Math.max(len, ends[cur]- start + 1);
                if(len >= (n - start + 1)) break;
                cur = ends[cur] + 1;
            }else{
                while(sum > k && start < n){
                    sum -= arr[start];
                    start++;
                }
                if(start >= n)
                    break;
                len = Math.max(len, ends[cur] - start + 1);
                cur = ends[cur] + 1;
            }
        }
        return len;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        System.out.print(getMaxLength1(arr, k));
    }
}

